#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
# http://www.careercup.com/question?id=6227714491023360
'''
suppose a string is consists of a, b, and c 
Now given a integer N, output the amount of all possible strings of length N that don't of have consecutive a,b,c. 
e.g. given N=5, string bacca is invalid since the first 3 letters have consecutive a,b,c. and bbbbb is valid.
'''

import os, re, sys, getopt
import logging
import locale
from utils import *

def all_possible_recur(full_set, n, s, result):
    #print s
    if len(s) == n:
        result.append(s)
        return

    size = len(full_set)
    valid_set = full_set
    exists = set()
    for i in xrange(len(s) -1, -1, -1):
        if s[i] in exists:
            break
        exists.add(s[i])
        if len(full_set.difference(exists)) == 1:
            valid_set = exists
            break

    #print s
    #print valid_set
    #print 
    for c in valid_set:
        all_possible_recur(full_set, n, s+c, result)
    return

@time_profile
def all_possible_lobatt(valid_set, n):
    result = []
    all_possible_recur(valid_set, n, '', result)
    return sorted(result)

def all_possible_david_help(valid_set, chars, n, result):
    if len(chars) == n:
        result.append("".join(chars))
    else:
        start_index = max(len(chars) - 2, 0)
        knowns_chars = set([])
        if len(chars): knowns_chars = set(chars[start_index:])
        for ch in valid_set:
            if len(knowns_chars) == 2 and ch not in knowns_chars: continue
            chars.append(ch)
            all_possible_david_help(valid_set, chars, n, result)
            chars.pop()

@time_profile
def all_possible_david(valid_set, n):
    result = []
    valid_set = set(valid_set)
    all_possible_david_help(valid_set, [], n, result)
    return sorted(result)

if __name__ == '__main__':
    valid_set = {'a','b','c'}
    for i in range(3, 8):
        check_result(all_possible_david, all_possible_lobatt, (valid_set, i))
